package com.haidechizi.sort;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{9, 11, 13, 56, 3, 4, 8, 15, 18, 65};
        mergeSort(arr, 0, arr.length - 1);
//        merge(arr, 0, 3, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }

    public static void merge(int[] arr, int start, int mid, int end) {
        int length = end - start + 1;
        int[] tempArr = new int[length];
        int low = start;
        int high = mid + 1;
        int index = 0;
        while (low <= mid && high <= end) {
            while (low <= mid && arr[low] <= arr[high]) {
                tempArr[index] = arr[low];
                low++;
                index++;
            }
            while (high <= end && arr[high] <= arr[low]) {
                tempArr[index] = arr[high];
                index++;
                high++;
            }
        }
        while (low <= mid) {
            tempArr[index] = arr[low];
            low++;
            index++;
        }

        while (high <= end) {
            tempArr[index] = arr[high];
            index++;
            high++;
        }

        for (int i = 0; i < length; i++) {
            arr[start + i] = tempArr[i];
        }

    }
}
